/*
https://www.lintcode.com/problem/subsets-ii/description
18. 子集 II
给定一个可能具有重复数字的列表，返回其所有可能的子集

样例
如果 S = [1,2,2]，一个可能的答案为：

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]
挑战
你可以同时用递归与非递归的方式解决么？

注意事项
子集中的每个元素都是非降序的
两个子集间的顺序是无关紧要的
解集中不能包含重复子集
*/

/*
解题思路：和17题一样的做法，加入使用set去重
*/

class Solution {
public:
    /**
     * @param nums: A set of numbers.
     * @return: A list of lists. All valid subsets.
     */
    vector<vector<int>> subsetsWithDup(vector<int> &nums) {
        // write your code here
        vector<vector<int> > result;
        vector<int> tmp;
    
        sort(begin(nums), end(nums));
        result.emplace_back(tmp);
        for (auto num : nums)
        {
            int cnt = result.size();
            for (int j = 0; j != cnt; ++j)
            {
                tmp = result[j];
                tmp.emplace_back(num);
                result.emplace_back(tmp);
                //resSet.insert(tmp);
            }
        }
    
        set<vector<int> > resSet(begin(result), end(result));    
        result.resize(resSet.size());
        copy(begin(resSet), end(resSet), begin(result));
    
        return result;
    }
};